package jjn.carl.monotonic_stack;

import java.util.Scanner;
import java.util.Stack;

/**
 * @author Jiang Jining
 * @since 2023-08-27 10:25
 */
public class LeetCode84 {
    public int largestRectangleArea(int[] heights) {
        int[] newHeight = new int[heights.length + 2];
        System.arraycopy(heights, 0, newHeight, 1, heights.length);
        newHeight[heights.length + 1] = 0;
        newHeight[0] = 0;
        
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        
        int res = 0;
        for (int i = 1; i < newHeight.length; i++) {
            while (newHeight[i] < newHeight[stack.peek()]) {
                int mid = stack.pop();
                int w = i - stack.peek() - 1;
                int h = newHeight[mid];
                res = Math.max(res, w * h);
            }
            stack.push(i);
            
        }
        return res;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int total = scanner.nextInt();
        int[] heights = new int[total];
        for (int i = 0; i < total; i++) {
            heights[i] = scanner.nextInt();
        }
        int largestRectangleArea = new LeetCode84().largestRectangleArea(heights);
        System.out.println(largestRectangleArea);
    }
}
